package cn.edu.jxau.test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * http://blog.csdn.net/luckyxiaoqiang/article/details/8937978
 * 
 * @author 付大石
 */
public class Main {

    public static void main(String[] args) throws CloneNotSupportedException {

        int[] arr1 = { 4, 5, 6, 7, 0, 1, 2 };
        System.out.println(binarySearchRotatedArrayKth(arr1, 4));
    }

    // ---------------------------------------------
    // 1.给定一个有序（非降序）数组A，求任意一个i使得A[i]等于target，不存在则返回-1
    // ---------------------------------------------
//    public static int binarySearch(int[] arr, int target) {
//
//        int low = 0;
//        int high = arr.length - 1;
//        int mid = 0;
//        while (low <= high) {
//            mid = low + ((high - low) >> 1);
//            if (arr[mid] < target) {
//                low = mid + 1;
//            } else if (arr[mid] > target) {
//                high = mid - 1;
//            } else {
//                return mid;
//            }
//        }
//        return -1;
//    }

    // ---------------------------------------------
    // 2.给定一个有序（非降序）数组A，可含有重复元素，求最小的i使得A[i]等于target，不存在则返回-1
    // ---------------------------------------------
//    public static int binarySearch(int[] arr, int key) {
//
//        int low = 0;
//        int high = arr.length - 1;
//        int mid = 0;
//        while (low <= high) {
//            mid = low + ((high - low) >> 1);
//            if (arr[mid] < key) {
//                low = mid + 1;
//            } else if (arr[mid] >= key) {
//                high = mid - 1;
//            }
//        }
//        return (low < arr.length && arr[low] == key) ? low : -1;
//    }

    // ---------------------------------------------
    // 3.给定一个有序（非降序）数组A，可含有重复元素，求最大的i使得A[i]等于target，不存在则返回-1
    // ---------------------------------------------
//    public static int binarySearch(int[] arr, int key) {
//
//        int low = 0;
//        int high = arr.length - 1;
//        int mid = 0;
//        while (low <= high) {
//            mid = low + ((high - low) >> 1);
//            if (arr[mid] <= key) {
//                low = mid + 1;
//            } else if (arr[mid] > key) {
//                high = mid - 1;
//            }
//        }
//        return high > -1 && arr[high] == key ? high : -1;
//    }

    // ---------------------------------------------
    // 4.给定一个有序（非降序）数组A，可含有重复元素，求最大的i使得A[i]小于target，不存在则返回-1
    // 也就是求小于target的最大元素的位置(floor)
    // ---------------------------------------------
//    public static int binarySearch(int[] arr, int key) {
//
//        int low = 0;
//        int high = arr.length - 1;
//        int mid = 0;
//        while (low <= high) {
//            mid = low + ((high - low) >> 1);
//            if (arr[mid] < key) {
//                low = mid + 1;
//            } else { //arr[mid]>=key
//                high = mid - 1;
//            }
//        }
//        return high;
//    }

    // ---------------------------------------------
    // 5.给定一个有序（非降序）数组A，可含有重复元素，求最小的i使得A[i]大于target，不存在则返回-1。
    // 也就是求大于target的最小元素的位置(ceiling)
    // ---------------------------------------------
//    public static int binarySearch(int[] arr, int key) {
//
//        int low = 0;
//        int high = arr.length - 1;
//        int mid = 0;
//        while (low <= high) {
//            mid = low + ((high - low) >> 1);
//            if (arr[mid] > key) {
//                high = mid - 1;
//            } else { // arr[mid] <= key
//                low = mid + 1;
//            }
//        }
//        return low >= arr.length ? -1 : low;
//    }

    // ---------------------------------------------
    // 6.给定一个有序（非降序）数组A，可含有重复元素，求target在数组中出现的次数
    // ---------------------------------------------
    public static int count(int[] arr, int key) {

        int firstIndex = getFirstIndex(arr, key);
        int lastIndex = getLastIndex(arr, key);
        if (firstIndex == -1) { // arr中不存在key
            return 0;
        }
        return lastIndex - firstIndex + 1;
    }

    private static int getFirstIndex(int[] arr, int key) {

        int low = 0;
        int high = arr.length - 1;
        int mid = 0;
        while (low <= high) {
            mid = low + ((high - low) >> 1);
            if (arr[mid] < key) {
                low = mid + 1;
            } else if (arr[mid] >= key) {
                high = mid - 1;
            }
        }
        return low < arr.length && arr[low] == key ? low : -1;
    }

    private static int getLastIndex(int[] arr, int key) {

        int low = 0;
        int high = arr.length - 1;
        int mid = 0;
        while (low <= high) {
            mid = low + ((high - low) >> 1);
            if (arr[mid] <= key) {
                low = mid + 1;
            } else if (arr[mid] > key) {
                high = mid - 1;
            }
        }
        return high > -1 && arr[high] == key ? high : -1;
    }

    // ---------------------------------------------
    // 8.给定一个有序（非降序）数组A，可含有重复元素，求绝对值最小的元素的位置
    // ---------------------------------------------
//    private static int getAbsMin(int[] arr) {
//
//        int low = 0;
//        int high = arr.length - 1;
//        int mid = 0;
//        while (low <= high) {
//            mid = low + ((high - low) >> 1);
//            if (arr[mid] < 0) {
//                low = mid + 1;
//            } else if (arr[mid] >= 0) {
//                high = mid - 1;
//            }
//        }
//        if (low <= 0) {
//            return low;
//        } else {
//            if (Math.abs(arr[low]) > Math.abs(arr[low - 1])) {
//                return low - 1;
//            } else {
//                return low;
//            }
//        }
//    }

    // ---------------------------------------------
    // 9.给定一个有序（非降序）数组A和一个有序（非降序）数组B，可含有重复元素，求两个数组合并结果中的第k(k>=0)个数字
    // ---------------------------------------------
    /**
     * 使用归并的方法求第k个元素，空间复杂度O(n),时间复杂度O(n)
     * 
     * @param arr1
     * @param arr2
     * @param pos
     * @return
     */
//    public static int item(int[] arr1, int[] arr2, int pos) {
//
//        int[] aux = new int[arr1.length + arr2.length];
//        int i = 0; // aux的索引值
//        int j = 0; // arr1的索引值
//        int k = 0; // arr2的索引值
//        for (; j < arr1.length && k < arr2.length; i++) {
//            if (arr1[j] < arr2[k]) {
//                aux[i] = arr1[j++];
//            } else {
//                aux[i] = arr2[k++];
//            }
//        }
//        while (j < arr1.length) {
//            aux[i++] = arr1[j++];
//        }
//        while (k < arr2.length) {
//            aux[i++] = arr2[k++];
//        }
//        System.out.println(Arrays.toString(aux));
//        return aux[pos];
//    }

    // ---------------------------------------------
    // 10.一个有序（升序）数组，没有重复元素，在某一个位置发生了旋转后，求target在变化后的数组中出现的位置，不存在则返回-1
    // 如 0 1 2 4 5 6 7 可能变成 4 5 6 7 0 1 2
    // ---------------------------------------------
    public static int binarySearchRotatedArray(int[] arr, int key) {

        int low = 0;
        int high = arr.length - 1;
        int mid = 0;
        while (low <= high) {
            mid = low + ((high - low) >> 1);
            if (arr[mid] == key) {
                return mid;
            } else if (arr[low] <= arr[mid]) { // low到mid有序
                if (key >= arr[low] && key < arr[mid]) { // key在[low,mid)范围内
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            } else { // mid到high有序
                if (key > arr[mid] && key <= arr[high]) { // key在(mid,high]范围内
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
        }
        return -1;
    }

    // ---------------------------------------------
    // 11.一个有序（升序）数组，没有重复元素，在某一个位置发生了旋转后，求最小值所在位置
    // ---------------------------------------------
    public static int binarySearchRotatedArrayMin(int[] arr) {

        int low = 0;
        int high = arr.length - 1;
        int mid = 0;
        while (low < high - 1) {
            mid = low + ((high - low) >> 1);
            if (arr[mid] < arr[low]) {
                high = mid;
            } else {
                low = mid;
            }
        }
        return arr[low] < arr[low + 1] ? low : low + 1;
    }
	
	private static int min(int[] arr) {

		int low = 0;
		int high = arr.length - 1;
		int mid = 0;
		while (low <= high) {
			mid = low + ((high - low) >> 1);
			if (arr[mid] <= arr[high]) {
				high = mid - 1;
			} else {
				low = mid + 1;
			}
		}
		return low < arr.length ? arr[low] : arr[low - 1];
	}

    // ---------------------------------------------
    // 12.一个有序（升序）数组，没有重复元素，在某一个位置发生了旋转后，求第k(k > 0)小元素的位置
    // ---------------------------------------------
    public static int binarySearchRotatedArrayKth(int[] arr, int k) {

        int min = binarySearchRotatedArrayMin(arr);
        return (min + k) % arr.length;
    }
}